import java.util.*;
class AnimalShelf {
    Queue<int[]> queue1;
    Queue<int[]> queue2;
    public AnimalShelf() {
        queue1=new LinkedList<int[]>();
        queue2=new LinkedList<int[]>();
    }

    public void enqueue(int[] animal) {
        if(animal[1]==0){
            queue1.add(animal);
        }else{
            queue2.add(animal);
        }
    }

    public int[] dequeueAny() {
        if(queue1.isEmpty()&&queue2.isEmpty()){
            return new int[]{-1,-1};
        }else if(queue1.isEmpty()){
            return queue2.poll();
        }else if(queue2.isEmpty()){
            return queue1.poll();
        }else{
            return queue1.peek()[0]>queue2.peek()[0]?queue2.poll():queue1.poll();
        }
    }

    public int[] dequeueDog() {
        if(queue2.isEmpty()){
            return new int[]{-1,-1};
        }
        return queue2.poll();
    }

    public int[] dequeueCat() {
        if(queue1.isEmpty()){
            return new int[]{-1,-1};
        }
        return queue1.poll();
    }
}











class MinStack {
    Stack<Integer> stack;
    Stack<Integer> stackmin;
    /** initialize your data structure here. */
    public MinStack() {
        this.stack=new Stack<>();
        this.stackmin=new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(stackmin.isEmpty()){
            stackmin.push(x);
        }else{
            if(stackmin.peek()>=x){
                stackmin.push(x);
            }
        }
    }

    public void pop() {
        int tmp=stack.pop();
        if(tmp==stackmin.peek()){
            stackmin.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return stackmin.peek();
    }
}





class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if(stack1.isEmpty()&&stack2.isEmpty()){
            return -1;
        }
        if(this.stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}







class TripleInOne {
    public int[] arr;
    public int size;
    public int index1,index2,index3;
    public TripleInOne(int stackSize) {
        this.size=stackSize;
        this.arr=new int[stackSize*3];
        index1=-1;
        index2=stackSize-1;
        index3=stackSize*2-1;
    }

    public void push(int stackNum, int value) {
        if(stackNum==0){
            if(index1+1<size){
                index1++;
                arr[index1]=value;
            }else{
                return;
            }
        }
        if(stackNum==1){
            if(index2+1<size*2){
                index2++;
                arr[index2]=value;
            }else{
                return;
            }
        }
        if(stackNum==2){
            if(index3+1<size*3){
                index3++;
                arr[index3]=value;
            }else{
                return;
            }
        }
    }

    public int pop(int stackNum) {
        if(stackNum==0&&index1>=0){
            index1--;
            return arr[index1+1];
        }
        if(stackNum==1&&index2>=size){
            index2--;
            return arr[index2+1];
        }
        if(stackNum==2&&index3>=size*2){
            index3--;
            return arr[index3+1];
        }
        return -1;
    }

    public int peek(int stackNum) {
        int sum=-1;
        if(stackNum==0&&index1>=0){
            sum=arr[index1];
        }
        if(stackNum==1&&index2>=size){
            sum=arr[index2];
        }
        if(stackNum==2&&index3>=size*2){
            sum=arr[index3];
        }
        return sum;
    }

    public boolean isEmpty(int stackNum) {
        if(stackNum==0&&index1==-1){
            return true;
        }
        if(stackNum==1&&index2==size-1){
            return true;
        }
        if(stackNum==2&&index3==size*2-1){
            return true;
        }
        return false;
    }
}





class MyQueue {
    public Stack<Integer> stack1;
    public Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty()&&stack2.isEmpty();
    }
}










class MinStack1 {
    public Stack<Integer> stack;
    public Stack<Integer> stackMin;
    /** initialize your data structure here. */
    public MinStack1() {
        this.stack=new Stack<>();
        this.stackMin=new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(stackMin.isEmpty()){
            stackMin.push(x);
        }else{
            if(stackMin.peek()>=x){
                stackMin.push(x);
            }
        }
    }
    public void pop() {
        if(stack.isEmpty()){
            return;
        }
        int tmp=stack.pop();
        if(tmp==stackMin.peek()){
            stackMin.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return stackMin.peek();
    }
}




class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
class RecentCounter {
    Queue<Integer> queue=new LinkedList<>();
    public RecentCounter() {

    }

    public int ping(int t) {
        int tmp=t-3000;
        while(!queue.isEmpty()&&queue.peek()<tmp){
            queue.poll();
        }
        queue.add(t);
        return queue.size();
    }
}


class Pair{
    int pos;
    char ch;

    public Pair(int pos, char ch) {
        this.pos = pos;
        this.ch = ch;
    }
}
class Solution {
    class Pair{
        int pos;
        char ch;

        public Pair(int pos, char ch) {
            this.pos = pos;
            this.ch = ch;
        }
    }
    public char firstUniqChar(String s) {
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        Queue<Pair> queue=new LinkedList<Pair>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(!map.containsKey(ch)){
                map.put(ch,i);
                queue.offer(new Pair(i,ch));
            }else{
                map.put(ch,-1);
                while(!queue.isEmpty()&&map.get(queue.peek().ch)==-1){
                    queue.poll();
                }
            }
        }
        return queue.isEmpty()?' ':queue.poll().ch;
    }





    List<Integer> list=new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if(root==null){
            return list;
        }
        list.add(root.val);
        for(Node r : root.children){
            preorder(r);
        }
        return list;
    }





    List<Integer> lists=new ArrayList<>();
    public List<Integer> postorder1(Node root) {
        if(root==null){
            return lists;
        }
        for(Node r :root.children){
            if(r!=null) {
                postorder1(r);
            }
        }
        lists.add(root.val);
        return lists;
    }






    public List<String> buildArray(int[] target, int n) {
        List<String> list=new ArrayList<>();
        int index=1;
        for(int i=0;i<target.length;i++){
            while(index!=target[i]){
                list.add("Push");
                list.add("Pop");
                index++;
            }
            list.add("Push");
            index++;
        }
        return list;
    }







    public int minOperations(String[] logs) {
        Stack<String> stack=new Stack<>();
        for(String s : logs){
            if(s.contains("../")&&!stack.isEmpty()){
                stack.pop();
            }else if(s.contains("./")){
                continue;
            }else{
                stack.push(s);
            }
        }
        return stack.size();
    }









    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb=new StringBuilder();
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)!='-'){
                sb.append(sb.length()%(k+1)==k?"-":"").append(s.charAt(i)>91?(char)(s.charAt(i)-32):s.charAt(i));
            }
        }
        return sb.reverse().toString();
    }







    public int[] sortArray(int[] nums) {
        if(nums.length==0){
            return nums;
        }
        for(int i=1;i<nums.length;i++){
            int tmp=nums[i];
            int j=i-1;
            for(;j>=0;j--){
                if(nums[j]>tmp){
                    nums[j+1]=nums[j];
                }else{
                    break;
                }
            }
            nums[j]=tmp;
        }
        return nums;
    }







    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> list=new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for(int i=0;i<Math.min(nums1.length,k);i++){

            for(int j=0;j<Math.min(nums2.length,k);j++){
                if(list.size()<k){
                    List<Integer> arr=new ArrayList<>();
                    arr.add(nums1[i]);
                    arr.add(nums2[j]);
                    list.offer(arr);
                }else{
                    List<Integer> top=list.peek();
                    int tmp=top.get(0)+top.get(1);
                    if(tmp>nums1[i]+nums2[j]){
                        list.poll();
                        List<Integer> arr=new ArrayList<>();
                        arr.add(nums1[i]);
                        arr.add(nums2[j]);
                        list.offer(arr);
                    }
                }
            }
        }
        List<List<Integer>> ret=new ArrayList<>();
        for(int i=0;i<k&&!list.isEmpty();i++){
            ret.add(list.poll());
        }
        return ret;
    }
}
